package main

import "fmt"

func main() {
	nums := []int{56, 1, 22, 23, 54, 16, 17, 9, 34}
	shellSort2(nums)
	fmt.Println(nums)
	shellSort(nums)
	fmt.Println(nums)
}

func shellSort(nums []int) {
	for gap := len(nums) / 2; gap >= 1; gap /= 2 {
		for i := gap; i < len(nums); i++ {
			for j := i; j-gap >= 0 && nums[j] < nums[j-gap]; j -= gap {
				nums[j], nums[j-gap] = nums[j-gap], nums[j]
			}
		}
	}
}

func shellSort2(nums []int) {
	for gap := len(nums) / 2; gap >= 1; gap /= 2 {
		for i := gap; i < len(nums); i++ {
			tmp := nums[i]
			var j int
			for j = i; j-gap >= 0 && nums[j-gap] > tmp; j = j - gap {
				nums[j] = nums[j-gap]
			}
			nums[j] = tmp
		}
	}
}
